// 给定一个未排序的整数数组nums，要求找出其中没有出现的最小的正整数，要求实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案

// 思路：对常熟空间复杂度，则需要使用数组本身作为映射，长度为n的数组可以映射[1, n]的正整数
// 遍历数组，把符合要求的正整数放到对应的位置，最终判断数组哪个不符合映射规则，则该结果就是没有出现的最小正整数
// 时间复杂度：O(n)，n是数组的长度
// 空间复杂度：O(1)

function firstMissingPositive(arr) {
    for (let i = 0; i < arr.length; i++) {
        // 这里必须循环判断，因为交换过来的整数需要判断是不是需要继续交换
        while (arr[i] >= 1 && arr[i] <= arr.length && arr[arr[i] - 1] !== arr[i]) {
            let index1 = i;
            let index2 = arr[i] - 1;
            [arr[index1], arr[index2]] = [arr[index2], arr[index1]];
        }        
    }
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] !== i + 1) {
            return i + 1
        }
    }
    return arr.length + 1
}

let nums = [3,4,9,1, -1,1,2]
nums = [3,4,-1,1]
console.log(firstMissingPositive(nums))